//https://leetcode.cn/problems/count-numbers-with-unique-digits/submissions/574032920/


class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        // 如果 n 为 0，则只有一个不重复的数字（空数字）
        if (n == 0)
            return 1;

        // dp 数组用于存储各位数的不重复数字数量
        vector<int> dp(n + 1);
        
        // 初始化：0 位数有 1 种情况（空），1 位数有 10 种情况（0-9）
        dp[0] = 1; 
        dp[1] = 10;

        // 动态规划计算不重复数字的数量
        for (int i = 2; i <= n; i++) {
            // 状态转移方程
            dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2]) * (10 - (i - 1));
            // dp[i-1] 表示 i-1 位数的不重复组合
            // (dp[i-1] - dp[i-2]) 是新增的组合方式
            // (10 - (i - 1)) 是可用的剩余数字
        }

        // 返回 n 位数的不重复组合数量
        return dp[n];
    }
};